Search results for "spanning trees"
showing 4 items of 4 documents
Minimum node weight spanning trees searching algorithm for broadcast transmission in sensor networks
2017
A minimum node weight spanning tree in a weighted, directed graph is a tree whose node with maximum out-weight is minimal among all spanning trees. This type of trees are important because they appear in the solutions of the maximum lifetime broadcasting problem in wireless sensor networks. In a complete graph build of N nodes there are NN-2 spanning trees and to find such trees it is necessary to perform more than O(NN-2) operations. In this paper we propose an algorithm for searching the minimum node weight spanning trees in the graph. In the proposed algorithm, instead of calculating the symbolic determinant of the generalized Laplacian matrix, numerical operations on its exponents are p…
Completely independent spanning trees in some regular graphs
2014
International audience; Let k >= 2 be an integer and T-1,..., T-k be spanning trees of a graph G. If for any pair of vertices {u, v} of V(G), the paths between u and v in every T-i, 1 <= i <= k, do not contain common edges and common vertices, except the vertices u and v, then T1,... Tk are completely independent spanning trees in G. For 2k-regular graphs which are 2k-connected, such as the Cartesian product of a complete graph of order 2k-1 and a cycle, and some Cartesian products of three cycles (for k = 3), the maximum number of completely independent spanning trees contained in these graphs is determined and it turns out that this maximum is not always k. (C) 2016 Elsevier B.V. All righ…
Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees
2017
International audience; The search of spanning trees with interesting disjunction properties has led to the introduction of edge-disjoint spanning trees, independent spanning trees and more recently completely independent spanning trees. We group together these notions by dening (i, j)-disjoint spanning trees, where i (j, respectively) is the number of vertices (edges, respectively) that are shared by more than one tree. We illustrate how (i, j)-disjoint spanning trees provide some nuances between the existence of disjoint connected dominating sets and completely independent spanning trees. We prove that determining if there exist two (i, j)-disjoint spanning trees in a graph G is NP-comple…
Image Segmentation through a Hierarchy of Minimum Spanning Trees
2012
Many approaches have been adopted to solve the problem of image segmentation. Among them a noticeable part is based on graph theory casting the pixels as nodes in a graph. This paper proposes an algorithm to select clusters in the images (corresponding to relevant segments in the image) corresponding to the areas induced in the images through the search of the Minimum Spanning Tree (MST). In particular is is based on a clustering algorithm that extracts clusters computing a hierarchy of Minimum Spanning Trees. The main drawback of this previous algorithm is that the dimension of the cluster is not predictable and a relevant portion of found clusters can be composed by micro-clusters that ar…